#include "junix.h"
#include <boost/bind.hpp>

int partition(int vec[], int lhs, int rhs) {
	int p = vec[rhs], l = lhs-1;
	for (int r=lhs;r<rhs;r++) {
		if (vec[r]<p) 
			std::swap(vec[++l], vec[r]);
	}

	std::swap(vec[++l], vec[rhs]);
	return l;
}

void quiksort(int vec[], int lhs, int rhs) {
	if (lhs>=rhs) return;
	int p = partition(vec, lhs, rhs);
	quiksort(vec, lhs,p-1);
	quiksort(vec,p+1, rhs);
}

int main(int argc, char **argv)
{
	const int sz=100000000;
	srand(time(0));
	std::vector<int> V(sz);
	generate(V.begin(),V.end(),
			boost::bind(std::modulus<int>(), boost::bind(rand), sz));
	jtime  T;
	T.start();
	quiksort(&V[0], 0, V.size()-1);
	//sort(V.begin(),V.end());
	T.end();
	T.print();

	std::vector<int>::iterator pos;
	pos=std::adjacent_find(V.begin(), V.end(), std::greater<int>());
	assert(pos==V.end());
}
